// Copyright 2011, Vanya Davidenko.
// Кодировка файла: UTF-8. 
package info.iu9.interval_tree;
import java.util.BitSet;
import java.util.Iterator;
import java.util.NoSuchElementException;



// Реализация интервального множества на основе битовых масок.
// Подходит только для множества, у которых невелика разность
// максимального элемента наибольшего интервала и минмального элемента
// наименьшего интервала, так как объект использует по меньшей мере такое
// количетсво бит.
public class BitSetIntervalSearchSet extends IntervalSearchSet {
  public static void main(String [] args) {
    BitSetIntervalSearchSet s = new BitSetIntervalSearchSet(0, 128);

    assert s.toString().isEmpty();
    assert !s.iterator().hasNext();
    assert !s.contains(0);

    s.add('a');
    assert s.toString().equals("a");
    assert s.iterator().next().equals((int)'a');
    assert !s.contains(0);
    assert s.contains((int)'a');

    s.add('b');
    assert s.toString().equals("ab");

    s.add('c');
    assert s.toString().equals("a-c");

    s.add('f');
    assert s.toString().equals("a-cf");

    s.add('m');
    assert s.toString().equals("a-cfm");

    s.add('n');
    assert s.toString().equals("a-cfmn");

    s.add('o');
    assert s.toString().equals("a-cfm-o");

    s.add('z');
    assert s.toString().equals("a-cfm-oz");

    s.add('0');
    assert s.toString().equals("0a-cfm-oz");

    final StringBuilder sb = new StringBuilder();
    for ( final int i : s ) {
      assert s.contains(i);
      sb.appendCodePoint(i);
    }
    assert sb.toString().equals("0abcfmnoz");
  }


  public Iterator iterator() {
    return new Iterator() {
      public void remove() { throw new UnsupportedOperationException(); }
      public boolean hasNext() { return set_.nextSetBit(cur_) != -1; }
      public Integer next() {
        if ( !hasNext() ) { throw new NoSuchElementException(); }
        final int r = set_.nextSetBit(cur_);
        cur_ = r + 1;
        return r + offset_;
      }
      private int cur_ = 0;
    };
  }


  public Object clone() {
    BitSetIntervalSearchSet r = null;
    try {
      r = (BitSetIntervalSearchSet)super.clone();
      r.set_ = (BitSet)set_.clone();
    } catch(CloneNotSupportedException e) { assert false; }
    return r;
  }


  public boolean contains(final int value) {
    if ( value < offset_ || value >= offset_ + size_ ) {
      return false;
    }
    return set_.get(value - offset_);
  }


  BitSetIntervalSearchSet(final int offset, final int size) {
    offset_ = offset;
    size_ = size;
    set_ = new BitSet(size);
  }

  void add(final int value) throws IllegalArgumentException {
    if ( value < offset_ || value >= offset_ + size_ ) {
      throw new IndexOutOfBoundsException("value is out of range");
    }
    set_.set(value - offset_);
  }


  private final int offset_;
  private final int size_;
  private BitSet set_;
}
